import random


def assign_cluster(x, centers):
    min_dist_sq = float('inf')
    cluster_idx = 0  # 最近聚类中心的索引

    for i, center in enumerate(centers):
        # 计算欧氏距离的平方(避免开方运算，提高效率)
        dist_sq = sum((xi - ci) ** 2 for xi, ci in zip(x, center))
        # 更新最小距离和对应索引
        if dist_sq < min_dist_sq:
            min_dist_sq = dist_sq
            cluster_idx = i
    return cluster_idx


def Kmeans(data, k, epsilon, iteration):
    # 输入合法性检查
    if not data:
        raise ValueError("样本集不能为空")
    if k <= 0 or k > len(data):
        raise ValueError("k必须为正数且不大于样本数量")

    # 检查所有样本维度是否一致
    n_features = len(data[0])
    for x in data:
        if len(x) != n_features:
            raise ValueError("所有样本必须具有相同的维度")

    # 1. 初始化聚类中心(从样本中随机选择k个不重复样本)
    n_samples = len(data)
    initial_indices = random.sample(range(n_samples), k)
    centers = [data[i].copy() for i in initial_indices]  # 复制避免修改原数据

    # 2. 迭代聚类过程
    for _ in range(iteration):
        # 2.1 为所有样本分配聚类标签
        labels = [assign_cluster(x, centers) for x in data]

        # 2.2 计算新的聚类中心
        new_centers = []
        for i in range(k):
            # 收集第i个聚类的所有样本
            cluster_samples = [data[j] for j in range(n_samples) if labels[j] == i]

            # 处理空聚类(若该聚类无样本，随机选择一个样本作为新中心)
            if not cluster_samples:
                new_center = random.choice(data).copy()
            else:
                # 计算每个维度的均值作为新中心
                new_center = []
                for d in range(n_features):
                    dimension_values = [s[d] for s in cluster_samples]
                    new_center.append(sum(dimension_values) / len(dimension_values))

            new_centers.append(new_center)

        # 2.3 检查是否收敛(计算中心最大变化量)
        max_change = 0.0
        for old, new in zip(centers, new_centers):
            # 计算欧氏距离
            dist = sum((o - n) ** 2 for o, n in zip(old, new)) ** 0.5
            if dist > max_change:
                max_change = dist

        # 若中心变化小于阈值，提前停止迭代
        if max_change < epsilon:
            centers = new_centers
            break

        # 更新聚类中心
        centers = new_centers

    # 计算最终的聚类标签
    final_labels = [assign_cluster(x, centers) for x in data]
    return centers, final_labels

# 测试数据（二维样本）
data = [
    [1, 2], [1, 3], [2, 1], [2, 3],  # 第一类
    [5, 6], [6, 5], [6, 7], [7, 6],  # 第二类
    [10, 11], [11, 10], [11, 12], [12, 11]  # 第三类
]

# 聚类（3个簇，收敛阈值0.001，最大迭代100次）
centers, labels = Kmeans(data, k=3, epsilon=1e-3, iteration=100)

print("最终聚类中心：")
for i, center in enumerate(centers):
    print(f"簇{i+1}：{center}")

print("\n样本聚类标签：")
for i, label in enumerate(labels):
    print(f"样本{data[i]} → 簇{label+1}")